import java.util.*;

public class Test {
    //后序中序还原二叉树
    public int postIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex=postorder.length-1;
        TreeNode root=buildTreechild(inorder,postorder,0,inorder.length-1);
        return root;
    }

    public TreeNode buildTreechild(int[] inorder, int[] postorder,
                                   int inBegin,int inEnd) {
        if (inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(postorder[postIndex]);

        int rootIndex=findRootdex(postorder,inorder);

        postIndex--;

        root.right=buildTreechild(inorder,postorder,rootIndex+1,inEnd);
        root.left=buildTreechild(inorder,postorder,inBegin,rootIndex-1);

        return root;
    }

    public int findRootdex(int[] postorder, int[] inorder){
        for (int i = 0; i < inorder.length; i++) {
            if (postorder[postIndex]==inorder[i]){
                return i;
            }
        }
        return -1;
    }

    //前序中序还原二叉树
    //若preIndex作为局部变量，preIndex参数在左右子树中都被增加了，没有考虑到下一个先序遍历元素的正确索引。
    //更改为成员变量即可解决
    public int preIndex;

    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        TreeNode root=buildTreechild(preorder,inorder,0,preorder.length-1);
        return root;
    }

    public TreeNode buildTreechild1(int[] preorder, int[] inorder,
                                   int inBegin,int inEnd) {
        if (inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(preorder[preIndex]);

        int rootIndex=findRootdex(preorder,inorder);

        preIndex++;

        root.left=buildTreechild(preorder,inorder,inBegin,rootIndex-1);
        root.right=buildTreechild(preorder,inorder,rootIndex+1,inEnd);

        return root;
    }

    /*public int findRootdex(int[] preorder, int[] inorder){
        for (int i = 0; i < inorder.length; i++) {
            if (preorder[preIndex]==inorder[i]){
                return i;
            }
        }
        return -1;
    }*/


    //前序遍历非递归
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                list.add(cur.val);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
        return list;
    }

    //中序遍历非递归
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            list.add(top.val);
            cur=top.right;
        }
        return list;
    }

    //后序遍历非递归 *
    //后序遍历之中有我们额外需要注意的点！！
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if (top.right==null||top.right==prev){
                stack.pop();
                list.add(top.val);
                prev=top;
            }else{
                cur=top.right;
            }
        }
        return list;
    }

    //寻找二叉树最近的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return root;
        }
        if (root==p||root==q){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if (leftTree!=null&&rightTree!=null){
            return root;
        }else if (leftTree!=null){
            return leftTree;
        }else{
            return rightTree;
        }
    }

    //**自底而上的层序遍历 和层序遍历逻辑一样，只做细微调整
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if (root==null){
            return null;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            List<Integer> curlist=new ArrayList<>();
            while(size>0){
                TreeNode cur=queue.poll();
                curlist.add(cur.val);
                if (cur.left!=null){
                    queue.offer(cur.left);
                }
                if (cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(0,curlist);//和正常次序的层序遍历的唯一区别在此
        }
        return ret;
    }

    //根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder stb=new StringBuilder();
        Creatstr(root,stb);
        return stb.toString();
    }

    public void Creatstr(TreeNode root,StringBuilder stb){
        if(root==null){
            return;
        }
        stb.append(root.val);
        if (root.left!=null){
            stb.append("(");
            Creatstr(root.left,stb);
            stb.append(")");
        }else{
            if (root.right==null){
                return;
            }else{
                stb.append("()");
            }
        }
        if (root.right==null){
            return;
        }else{
            stb.append("(");
            Creatstr(root.right,stb);
            stb.append(")");
        }
    }

}
